package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href="https://leetcode.cn/problems/lru-cache/">LRU 缓存(LRU Cache)</a>
 * <p>请你设计并实现一个满足<a href="https://baike.baidu.com/item/LRU">LRU (最近最少使用) 缓存</a>约束的数据结构。</p>
 * <p>实现 LRUCache 类：
 * <ul>
 * <li>LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存</li>
 * <li>int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。</li>
 * <li>void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。</li>
 * </ul>
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * </p>
 * <p>
 *     <b>示例：</b>
 *     <pre>
 * 输入
 *      ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
 *      [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
 * 输出
 *      [null, null, null, 1, null, -1, null, -1, 3, 4]
 * 解释
 *      LRUCache lRUCache = new LRUCache(2);
 *      lRUCache.put(1, 1); // 缓存是 {1=1}
 *      lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
 *      lRUCache.get(1);    // 返回 1
 *      lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
 *      lRUCache.get(2);    // 返回 -1 (未找到)
 *      lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
 *      lRUCache.get(1);    // 返回 -1 (未找到)
 *      lRUCache.get(3);    // 返回 3
 *      lRUCache.get(4);    // 返回 4
 *     </pre>
 * </p>
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>1 <= capacity <= 3000</li>
 *         <li>0 <= key <= 10000</li>
 *         <li>0 <= value <= 10^5</li>
 *         <li>最多调用 2 * 10^5 次 get 和 put</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0460LFUCache_H LFU 缓存(LFU Cache)
 * @since 2023/5/4 9:38
 */
public class LC0146LRUCache_M {

    static class LRUCache {
        /**
         * 最大容量
         */
        private final int capacity;
        private final Map<Integer, Node> cache;

        private final Node head;
        private final Node tail;


        public LRUCache(int capacity) {
            this.capacity = capacity;
            cache = new HashMap<>(capacity);
            // 创建两个伪节点head和tail
            head = new Node();
            tail = new Node();
            head.next = tail;
            tail.prev = head;
        }

        /**
         * 对于 get 操作，首先判断 key 是否存在：
         * <ul>
         *     <li>如果 key 不存在，则返回 −1；</li>
         *     <li>如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。</li>
         * </ul>
         */
        public int get(int key) {
            Node node = cache.get(key);
            if (node == null) {
                return -1;
            }
            moveNodeToHead(node);
            return node.value;
        }

        /**
         * 对于 put 操作，首先判断 key 是否存在：
         * <ul>
         *     <li>如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；</li>
         *     <li>如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。</li>
         * </ul>
         */
        public void put(int key, int value) {
            // 判断当前值在缓存中是否存在：如果存在，更新val即可，并将当前节点移动到链表头
            Node node = cache.get(key);
            if (node == null) {
                node = new Node(key, value);
                // 判断当前值在缓存中是否存在：如果不存在,判断缓存是否已满
                if (cache.size() == capacity) {
                    cache.remove(removeNodeFromTail().key);
                }
                addNodeToHead(node);
                cache.put(key, node);
            } else {
                node.value = value;
                moveNodeToHead(node);
            }
        }

        private void addNodeToHead(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        private void moveNodeToHead(Node node) {
            if (node.prev == head) {
                return;
            }
            node.next.prev = node.prev;
            node.prev.next = node.next;
            addNodeToHead(node);
        }

        private Node removeNodeFromTail() {
            Node node = tail.prev;
            node.prev.next = node.next;
            node.next.prev = node.prev;
            return node;
        }

        static class Node {
            int key;
            int value;
            Node next;
            Node prev;

            public Node() {
            }

            public Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 0);
        cache.put(2, 2);
        System.out.println(cache.get(1));
        cache.put(3, 3);
        System.out.println(cache.get(2));
        cache.put(4, 4);
        System.out.println(cache.get(1));
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
    }

    //public static void main(String[] args) {
    //    LRUCache cache = new LRUCache(10);
    //    cache.put(10, 13);
    //    cache.put(3, 17);
    //    cache.put(6, 11);
    //    cache.put(10, 5);
    //    cache.put(9, 10);
    //    cache.get(13);
    //    cache.put(2, 19);
    //    cache.get(2);
    //    cache.get(3);
    //    cache.put(5, 25);
    //    cache.get(8);
    //    cache.put(9, 22);
    //    cache.put(5, 5);
    //    cache.put(1, 30);
    //    cache.get(11);
    //    cache.put(9, 12);
    //    cache.get(7);
    //    cache.get(5);
    //    cache.get(8);
    //    cache.get(9);
    //    cache.put(4, 30);
    //    cache.put(9, 3);
    //    cache.get(9);
    //    cache.get(10);
    //    cache.get(10);
    //    cache.put(6, 14);
    //    cache.put(3, 1);
    //    cache.get(3);
    //    cache.put(10, 11);
    //    cache.get(8);
    //    cache.put(2, 14);
    //    cache.get(1);
    //    cache.get(5);
    //    cache.get(4);
    //    cache.put(11, 4);
    //    cache.put(12, 24);
    //    cache.put(5, 18);
    //    cache.get(13);
    //    cache.put(7, 23);
    //    cache.get(8);
    //    cache.get(12);
    //    cache.put(3, 27);
    //    cache.put(2, 12);
    //    cache.get(5);
    //    cache.put(2, 9);
    //    cache.put(13, 4);
    //    cache.put(8, 18);
    //    cache.put(1, 7);
    //    cache.get(6);
    //    cache.put(9, 29);
    //    cache.put(8, 21);
    //    cache.get(5);
    //    cache.put(6, 30);
    //    cache.put(1, 12);
    //    cache.get(10);
    //    cache.put(4, 15);
    //    cache.put(7, 22);
    //    cache.put(11, 26);
    //    cache.put(8, 17);
    //    cache.put(9, 29);
    //    cache.get(5);
    //    cache.put(3, 4);
    //    cache.put(11, 30);
    //    cache.get(12);
    //    cache.put(4, 29);
    //    cache.get(3);
    //    cache.get(9);
    //    cache.get(6);
    //}
}
